/*
 * @lc app=leetcode.cn id=106 lang=swift
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        if inorder.isEmpty || postorder.isEmpty { return nil }

        func build(_ inorder: [Int], _ inStart: Int, _ inEnd: Int,
                   _ postorder: [Int], _ postStart: Int, _ postEnd: Int
        ) -> TreeNode? {
            if inStart > inEnd { return nil }

            let rootVal = postorder[postEnd]
            var inIndex = 0
            for i in inStart...inEnd {
                if inorder[i] == rootVal {
                    inIndex = i
                    break
                }
            }

            let leftSize = inIndex - inStart
            let root = TreeNode(rootVal)
            root.left = build(inorder, inStart, inIndex-1,
                              postorder, postStart, postStart+leftSize-1)
            root.right = build(inorder, inIndex+1, inEnd,
                              postorder, postStart+leftSize, postEnd-1)

            return root
        }

        return build(inorder, 0, inorder.count - 1,
                     postorder, 0, postorder.count-1)
    }
}
// @lc code=end

